package com.fosss.search;

/**
 * 插值查找，与二分查找相比在mid的求法上做了改变
 * 对于数据量较大，关键字分布比较均匀的查找来说，查找次数少，速度快
 * 关键字分布不均匀的情况下，该方法不一定比折半查找好
 */
public class InsertValueSearch {
    public static void main(String[] args) {

        int[] arr=new int[100];

        for (int i = 0; i < 100;i++) {
            arr[i]=i+1;
        }
        int index = insertValueSearch(arr, 0, arr.length - 1, 100);
        System.out.println(index);
    }

    public static int insertValueSearch(int[] arr,int left,int right,int value) {
        if (left > right || value < arr[0] || value > arr[arr.length - 1]) {//value<arr[0]||value>arr[arr.length - 1]防止下边求mid时数值过大而越界
            return -1;
        }
        int mid =left+(value-arr[left])/(arr[right]-arr[left])*(right-left);
        int midValue=arr[mid];

        if(value<midValue){
            //向左递归
            insertValueSearch(arr,left,mid-1,value);
        }else if(value>midValue){
            //向右递归
            insertValueSearch(arr,mid+1,right,value);
        }else {
            return mid;
        }
        return -1;
    }
}














